import java.util.ArrayList;
import java.util.List;

public class Solution {
    public static void main(String[] args) {
        String s = "cbaebabacd";
        String p = "abc";
        System.out.println(findAnagrams(s, p));
    }
    //字符串所有异位词
    public static List<Integer> findAnagrams(String s, String p) {
        int n = s.length();
        int m = p.length();
        int right = 0;
        int left = 0;
        int[] hash1 = new int[26];
        int[] hash2 = new int[26];
        List<Integer> list = new ArrayList<>();
        //p的元素放入hash表中
        for (int i = 0; i < m; i++) {
            hash2[p.charAt(i) - 'a']++;
        }
        while (right < n) {
            //进入窗口
            hash1[s.charAt(right) - 'a']++;
            //判断出窗口
            if(right - left + 2 > m){
                //更新结果
                if(check(hash1,hash2)) {
                    list.add(left);
                }
                hash1[s.charAt(left) - 'a']--;
                left++;
                right++;
            }else{
                right++;
            }
        }
        return list;
    }
    public static boolean check(int[] hash1, int[] hash2) {
        for(int i = 0; i < 26; i++) {
            if(hash1[i] != hash2[i]) {
                return false;
            }
        }
        return true;
    }
}
